
import Foundation

/*
 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

// 旋转数组，找到旋转点位  二分查找的思想
func minArray(_ numbers: [Int]) -> Int {
    return searchIndex(numbers, 0, numbers.count-1)
}

func searchIndex(_ numbers: [Int], _ left:Int, _ right: Int) -> Int {
    if left >= right {
        return numbers[left]
    }
    let mid = (right-left)/2 + left
    
    if numbers[mid] < numbers[right] {
        //从mid点开始向后查找
        return searchIndex(numbers, left, mid)
    } else if numbers[mid] > numbers[right] {
        return searchIndex(numbers, mid+1, right)
    } else {
        return searchIndex(numbers, left, right-1)
    }
}

minArray([2,2,2,0,1,1,1,1])
minArray([1])
minArray([1,2,3,4])
minArray([3,1,1])
